【题解】[洛谷 P4514]上帝造题的七分钟

发表于 | 分类于 | 误人子弟 个
字数统计: 1,074 | 阅读时长 ≈ 5

对树状数组不了解的同学戳这里 —> 【模板】树状数组

题目背景

裸体就意味着身体。

*tips:作为一道严肃题目的背景，这句话显然是非常重要的（我总不能说吸引读者注意，激发读者阅读兴趣吧咳咳…）

题目描述

第一分钟，X说，要有矩阵，于是便有了一个里面写满了 0 的 n×m 矩阵。
第二分钟，L说，要能修改，于是便有了将左上角为 (a,b) ，右下角为 (c,d) 的一个矩形区域内的全部数字加上一个值的操作。
第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。
第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。
第五分钟，和雪说，要有耐心，于是便有了时间限制。
第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。
——《上帝造裸题的七分钟》
所以这个神圣的任务就交给你了。

输入输出格式

输入格式：

输入数据的第一行为X n m，代表矩阵大小为 n×m 。
从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：

L a b c d delta —— 代表将以 (a,b),(c,d) 为顶点的矩形区域内的所有数字加上delta。
k a b c d —— 代表求以 (a,b),(c,d) 为顶点的矩形区域内所有数字的和。
请注意， k 为小写。

输出格式：

针对每个 k 操作，在单独的一行输出答案。

输入输出样例

输入样例#1：

X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3

输出样例#1：

12

思路

没有思路的，这就是一道二维树状数组（区间修改 + 区间查询）的裸题，题目卡二维线段树，所以还是好好写二维树状数组吧

什么？你不会二维树状数组？不(我)好意(懒)思(啊)，没看到这是题解（懒得写模板）吗…

本题主要考察二维树状数组的区间修改 + 区间查询（可以参考一维树状数组的类似做法）
别忘了，裸题就意味着神题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
typedef long long ll;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch>'9' or ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' and ch<='9'){x=10*x+ch-'0';ch=getchar();}
	return f*x;
}
inline ll lowbit(ll x){
	return x & (-x);
}
int n,m,d1[2100][2100],d2[2100][2100],d3[2100][2100],d4[2100][2100];
inline void sum_add(int x,int y,int z){
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=m;j+=lowbit(j)){
			d1[i][j]+=z;
			d2[i][j]+=z*x;
			d3[i][j]+=z*y;
			d4[i][j]+=z*x*y;
		}
}
inline void range_add(int xa,int ya,int xb,int yb,int z){   //区间修改（只需要修改四个点）
	sum_add(xa,ya,z);
	sum_add(xa,yb+1,-z);
	sum_add(xb+1,ya,-z);
	sum_add(xb+1,yb+1,z);
}
inline int sum_ask(int x,int y){        //(1,1)与(x,y)的区间和（二维前缀和）
	int ans=0;
	for(int i=x;i;i-=lowbit(i))
		for(int j=y;j;j-=lowbit(j)){
			ans +=(x+1)*(y+1)*d1[i][j]
				- (y+1)*d2[i][j]
				- (x+1)*d3[i][j]
				+ d4[i][j];
		}
	return ans;
}
inline int range_ask(int xa,int ya,int xb,int yb){      //区间查询
	return sum_ask(xb,yb)-sum_ask(xb,ya-1)-sum_ask(xa-1,yb)+sum_ask(xa-1,ya-1);
}
char opt[10];
int main(){
	scanf("X%d%d",&n,&m);
	while(~scanf("%s",&opt)){
		if(opt[0]=='L'){
			int xa,ya,xb,yb,z;
			scanf("%d%d%d%d%d",&xa,&ya,&xb,&yb,&z);
			range_add(xa,ya,xb,yb,z);
		}
		if(opt[0]=='k'){
			int xa,ya,xb,yb;
			xa=read(),ya=read(),xb=read(),yb=read();
			printf("%d\n",range_ask(xa,ya,xb,yb));
		}
	}

	return 0;
}

题目来源

洛谷 P4514 上帝造题的七分钟

0%